// Copyright 2011-2012, Vanya Davidenko.
// Используемая кодировка: UTF-8.

#ifndef LIBV_BOOST_XML_DEPTH_FIRST_XML_NODE_ITERATOR_H_
#define LIBV_BOOST_XML_DEPTH_FIRST_XML_NODE_ITERATOR_H_

#include <algorithm>
#include <deque>
#include <iterator>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/lambda/lambda.hpp>
#include <libv/boost/xml/xml_node.h>
#include <libv/check.h>



namespace libv {

// Итератор, обходящий вершины в глубину, начиная с детей переданной вершины.
// Передаваемый предикат позволяет ограничить глубину (true, если можно глубже).
template <class TDepthLimitTagPred>
class DepthFirstXmlNodeIterator
    : public boost::iterator_facade<
          DepthFirstXmlNodeIterator<TDepthLimitTagPred>,
          const XmlNode,
          ::std::forward_iterator_tag,
          const XmlNode> {
  friend class boost::iterator_core_access;
  public:
    DepthFirstXmlNodeIterator() {
        assert(AtEnd());
    }

    // Итератор, обходящий вершины в глубину.
    DepthFirstXmlNodeIterator(const XmlNode& node,
                              const TDepthLimitTagPred& pred)
      : pred_(pred) {
        if ( !node.IsNull() && !pred_(node) ) {
            stack_.push_back(node.ChildrenBegin());
        }
    }

    // Проверка достижения итератором конца.
    bool AtEnd() const {
        return stack_.empty();
    }

  private:
    void increment() {
        LIBV_PRECOND(!AtEnd());

        // Можно опускаться ниже
        if ( !pred_(*stack_.back()) && stack_.back()->HasChild(NULL) ) {
            stack_.push_back(stack_.back()->ChildrenBegin());
            return;
        }

        ++stack_.back();

        while ( stack_.back().AtEnd() ) {
            stack_.pop_back();
            if ( stack_.empty() ) {
                return;
            }
            ++stack_.back();
        }
    }

    // Метод возвращает значение, так как XmlNode по своей сути является
    // указателем, но возвращаемый объект в данном случае — proxy.
    const XmlNode dereference() const {
        LIBV_PRECOND(!AtEnd());
        return *stack_.back();
    }

    // Учитывается только текущее состояние, но не предикат.
    bool equal(const DepthFirstXmlNodeIterator& rhv) const {
        if ( AtEnd() && rhv.AtEnd() ) {
            return true;
        }
        return stack_.size() == rhv.stack_.size() &&
               ::std::equal(stack_.begin(), stack_.end(), rhv.stack_.begin());
    }

    ::std::deque<XmlNode::Iterator> stack_;
    TDepthLimitTagPred pred_;
};

}  // libv

#endif  // LIBV_BOOST_XML_DEPTH_FIRST_XML_NODE_ITERATOR_H_
